import java.util.Scanner;

public class Pyramid {
    //观察下面的数字金字塔。
    // 写一个程序查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。
    // 每一步可以从当前点走到左下方的点也可以到达右下方的点。第一行的输入为金字塔的层数

    /*示例1：
    输入：
    5
    7
    3 8
    8 1 0
    2 7 4 4
    4 5 2 6 5

    输出：
    30*/

    /*示例2：
    5
    13
    11 8
    12 7 26
    6 14 15 8
    12 7 13 24 11
    输出:86*/

    //思路：对于每一步而言，此时的最优解每一个子步骤进行的是判断当前的最大值
    //此时需要返回的是前一个状态后累加的最大值，简单来说就是下一个答案与上一个答案有关系，
    // 并且依赖于前一个答案

    public static int SumMax(int[][] a) {
        int[][] f = new int[a.length+1][a.length+1];
        //这里的f[i][j]数组的定义为遍历到第i'行第j列的值时累计的最大值
        //开辟一个空间进行存储计算后的数据。
        // 边界
        int i,j;
        for (i=0; i<a.length; i++) {
            f[a.length-1][i] = a[a.length-1][i];//进行复制初始化为最底下的值，自底向上进行动态规划
        }

        //把数据进行转移
        for (i=a.length-1; i>=0; i--) { //行
            for (j=0;j<=i;j++) { //列

                int max = Math.max(f[i+1][j+1],f[i+1][j]); //下方、右下方
                f[i][j] = max + a[i][j];
//                System.out.println(f[i][j]);
            }
        }
        return f[0][0];
    }
    public static void main(String[] args){
//        int[][]a={{7},{3,8},{8,1,0},{2,7,4,4},{4,5,2,6,5}};
        Scanner in=new Scanner(System.in);
        //输入需要计算的金字塔的层数
        System.out.print("请输入需要计算的金字塔的层数是：");
        int n=in.nextInt();

        int[][] p=new int[n][];
        for(int i=0;i<n;i++){
            p[i]=new int[i+1]; //每行的列数进行递增
            for(int j=0;j<=i;j++){
                p[i][j]=in.nextInt();
            }
        }
        System.out.println("改金字塔路径的最大数字和为：" + SumMax(p));
    }
}
